Section: New Results

Network Design and Optimization

Participants : Jean-Claude Bermond, Nathann Cohen, David Coudert, Frédéric Giroire, Dorian Mazauric, Joanna Moulierac, Nicolas Nisse, Ronan Pardo Soares, Issam Tahiri.

Backbone and Broadband Networks

Network design is a very wide subject that concerns all kinds of networks. We mainly study telecommunications networks which can be either physical networks (backbone, access, wireless, ...) or virtual (logical) ones. The objective is to design a network able to route a (given, estimated, dynamic, ...) traffic under some constraints (e.g. capacity) and with some quality of service (QoS) requirements. Usually the traffic is expressed as a family of requests with parameters attached to them. In order to satisfy these requests, we need to find one (or many) path(s) between their end nodes. The set of paths is chosen according to the technology, the protocol or the QoS constraints. For instance, optical backbones use the WDM technology to take better advantage of the capacity of the optical fibers often already installed. This is achieved through the multiplexing of several wavelength channels onto the same fiber. In that case a resource allocation is an optical channel, also called lightpath, which includes a path and wavelengths assigned to its links, one per link. If wavelength translation is performed in optical switching, then each channel may be assigned different wavelengths on the links of its path; otherwise the wavelength continuity imposes all the links to have the same wavelength. Of course, two lightpaths sharing a link must use different wavelengths on that link. The design can be done at the conception of the network (i.e. when conceiving a virtual network in MPLS where we have to establish virtual paths) or to adapt the network to changes (failures, new link, updates of routers, variation of traffic, ...). Finally there are various optimization criteria which differ according to the point of view: for a network user they are related to his/her satisfaction (minimizing delays, increasing available bandwidth, ...), while for a network operator, economics criteria like minimizing deployment and operating costs are more important.

This very wide topic is addressed by a lot of academic and industrial teams in the world. Our approach is to attack these problems with tools from Discrete Mathematics.

Traffic Grooming

In a WDM network, routing a connection request consists in assigning to this request a route in the physical network and a wavelength. When each request uses at most $1/C$ of the bandwidth of the wavelength, we say that the grooming factor is $C$. It means that on a given link of the network we can groom at most $C$ requests on the same wavelength. Under this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or to minimize the number of Add/Drop Multiplexers (ADM) used in the network (related to the cost of the nodes). During the last years, we have addressed this problem in various WDM network topologies with the goal of minimizing the total number of required ADMs.

This year, we considered the minimization of the number of ADMs in optical WDM bidirectional rings, considering symmetric shortest path routing and all-to-all unitary requests [24] . We formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We have studied exhaustively the cases $C=1$, $C=2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We have also studied the case $C>3$, focusing specifically on the case $C=k(k+1)/2$ for some $k\ge 1$. We have also proposed optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs.

Routing Reconfiguration and its Links with Graph Searching

In production networks, traffic evolution, failures and maintenance operations force to adapt regularly the current configuration of the network (virtual topology, routing of connections). The routing reconfiguration problem in WDM networks is thus to schedule the migration of established lightpaths from current routing to a new pre-computed one while minimizing service disruptions. We have shown in the past the relations between this problem and the graph searching problem (see also Section  6.4.3 ).

This year, we have continued studying the tradeoffs between the total number and the number of simultaneous interruptions that occurs during the reconfiguration process, proving in particular that the knowledge of one parameter does not help to optimize the other [28] , [15] . We have also started investigating the influence of physical layer impairment constraints on the reconfiguration problem [74] . More precisely, using a new wavelength in a fiber of a WDM network forces to tune or recalibrate all already used wavelengths. We thus model the cost of using a new wavelength with a linear function of the number of already used wavelengths. We have then studied the problem of minimizing the cost of the reconfiguration according to this function. We have shown that this optimization problem is already NP-complete in a two-node network. We have also obtained general bounds and characterized instances for which the problem can be solved in polynomial time. We have additionaly proposed and evaluated heuristics.

Green Networking

The minimization of ICT (Information and Communications Technologies) energy consumption has become a priority with the recent increase of energy cost and the new sensibility of public, governments and corporations towards energy consumption. ICT alone is responsible of 2% to 10% (depending on the estimations) of the world power consumption. For example, it is estimated that switches, hubs, routers account for 6 TWh per year in the US.

Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis, etc. In [78] , [15] , we have defined and modeled formally the problem of finding a routing that minimizes the (weighted) number of active network elements. We have proved that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm to solve it. We have obtained general bounds for this problem, and bounds for particular topologies such as trees, grids, and cliques. We have also proposed a heuristic algorithm offering good performance on real topologies. Last, we have analyzed the impact of energy efficient routing on the stretch factor and on fault tolerance.

We have also studied potential energy savings in fixed broadband wireless networks [77] , [61] . See Section  6.1.2.1 for more details.

Xcast6 Treemap Islands

IP multicast is a protocol that deals with group communications with the aim of reducing traffic redundancy in the network. However, due to difficulty in deployment and poor scalability with a large number of multicast groups, IP multicast is still not widely deployed nor used on the Internet. Recently, Xcast6 and Xcast6 Treemap, the two network layer multicast protocols, have been proposed with complementary scaling properties to IP multicast: they support a very large number of active multicast sessions. However, the key limitation of these protocols is that they only support small multicast groups. To overcome this limitation, we have proposed the Xcast6 Treemap Island [96] , a hybrid model of Application Layer Multicast (ALM) and Xcast6 that can work for large multicast groups. Our model has several advantages: ease of deployment, efficiency in bandwidth savings, no control message between end-host and router, zero multicast forwarding state at router and no need for a multicast address allocation protocol. In addition, this model is a potential service from which an ISP (Internet Service Provider) can get new revenue. We have shown the feasibility of our model by simulation and comparison with IP multicast and NICE protocols.

Time-Dependent Graphs - Applications to Transport Networks

In [70] , we focus on time-dependent graphs which seem to be a good way to model transport networks. In the first part, we remind some notations and techniques related to time-dependent graphs. In the second one, we introduce new algorithms to take into account the notion of probability related to paths in order to guarantee travelling times with a certain accuracy. We also discuss different probabilistic models and show the links between them.

Other results on multi-interface networks were obtained outside of Mascotte  [37] , [36] , [65] , [63] , [66] , [52] , [20] .

Wireless Networks

Mascotte has conducted an intense research effort on wireless access networks. From the technological and architectural point of view, the field is broad, from mesh (or multi-hop cellular) networks to ad-hoc and sensor networks. Nevertheless, many questions and approaches are generic from an algorithmic and structural prospect. In particular, we have considered three of the most prominent performance metrics for radio networks. Using combinatorial optimization and centralized algorithmic with a network design flavor, fast data gathering, call scheduling, transport capacity and energy consumption of the networks have been studied. Our approach is complementary with those developed in other INRIA project-teams such as Planete , Maestro , Swing , or Pops . The complementarity has been exploited through a joint Ph.D. between Maestro and Mascotte  [15] , through an ANR VERSO project in which Maestro , Mascotte , and Swing are involved, and through regular collaborations with Pops . At the international level, we cooperate with some groups in renowned research centers such as CTI of Patras in Greece, RWTH Aachen in Germany, Universities of Roma or Salerno in Italy, the Technion Institute in Israël, SFU in Vancouver, Canada, UFC Universidade Federal do Ceará, Fortaleza, Brazil, or the University of Sao Paulo in Brazil. We studied a wide range of issues of wireless networks, from the design of efficient cross-layer medium access, call scheduling and routing techniques to energy efficient optimization. We developed theoretical tools for integrating dynamic caracteristics of the networks in the optimization models, and analyzing and evaluating dynamic networks. Some graph coloring problems motivated by channel assignment in wireless networks are detailed in Section  6.3 .

Wireless Backhaul

We have investigated network optimization problems related to the design and configuration of fixed wireless microwave backhaul - the portion of the network infrastructure that provides interconnectivity between the access and the core networks. Unlike wired networks, the capacity of a microwave radio link is prone to variations, either due to external factors (e.g., weather) or by the action of the network operator. This fundamental difference raises a variety of new issues to be addressed appropriately. We concentrated on conceiving reliable fixed broadband wireless networks under outage probability constraints [60] , [59] . We have developed a joint optimization of data routing and bandwidth assignment that minimizes the total renewal fees of licenses, while handling all the traffic requirements simultaneously. We have proposed a chance-constrained mathematical program taking into account unreliable channel conditions. This approach remains one of the main challenges of modern stochastic programming and it is still considered as very difficult and widely intractable. We have derived integer linear programming (ILP) counterparts for these chance-constrained programs and propose cutset-based valid inequalities to enhance the performance of ILP solvers. Computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations. Moreover, we have been interested in potential energy savings in fixed broadband wireless networks by selectively turning off idle communication devices in low-demand scenarios [77] , [61] . We have proposed a mathematical formulation of the problem relying on a fixed-charge capacitated network design (FCCND) problem, which is very hard to optimize. We have derived from this modeling heuristic algorithms producing feasible solutions in a short time. This work was done in collaboration with the SME 3Roam, and partially developed within the scope of the joint project RAISOM (Réseaux de collecte IP sans fil optimisés).

Wireless Mesh Networks

We have addressed the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access [26] . Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross-layer optimization of these problems allows the routing to take into account contentions due to radio interference. We have presented a generic Mixed Integer Linear Programing (MILP) addressing gateway placement, routing, and scheduling optimizations in a WMN. We have then derived new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the computation to a bounded area. It allows for computing solutions very efficiently on large networks. We have then extended our models to deal with the dynamic caracteristics of the network [75] . We have proposed a new robust optimization model that considers traffic demand uncertainty, in order to compute an optimal robust routing and bandwidth allocation in WMNs. We have presented a linear program efficiently solved by column generation, and we have quantified the price of robustness, i.e. the additional cost to pay in order to obtain a feasible solution for the robust scheme.

We have additionally investigated on the feasibility of providing network connectivity to vehicles over a predefined trajectory (trains, metros, urban buses, etc.) [14] . The communication between the vehicle and the infrastructure network is based only on WiFi technology. The contributions of this work are two-fold: 1) the horizontal handover (between WiFi access points) and 2) the design and analysis of an infrastructure network (backbone network plus WiFi access network) deployed along the trajectory of the vehicle.

Data Gathering

We have studied algorithmic and complexity issues originating from the problem of data gathering in wireless networks [56] . We give an algorithm to construct minimum makespan transmission schedules for data gathering when the communication graph is a tree network, the interference range is any integer $m\ge 2$, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is weakly NP-complete. On the positive side, we design a simple $(1+2/m)$ factor approximation algorithm for general networks. We have also considered the data gathering process in multi-hop wireless sensor networks [76] , [57] . Wireless sensors networks (WSNs) are deployed to collect huge amounts of data from the environment. This produced data has to be delivered through sensor's wireless interface using multi-hop communications toward a sink. The position of the sink impacts the performance of the wireless sensor network regarding delay and energy consumption especially for relaying sensors. Optimizing the data gathering process in multi-hop wireless sensor networks is, therefore, a key issue. We have addressed the problem of data collection using mobile sinks in a WSN. We provide a multi-objective optimization framework that studies the trade-off between energy consumption and delay of data collection. This framework provides solutions that allow decision makers to optimally design the data gathering plan in wireless sensor networks with mobile sinks.

P2P Networks

Performance Analysis of Distributed Storage Systems

Distributed or peer-to-peer storage solutions rely on the introduction of redundant data to be fault-tolerant and to achieve high reliability. To ensure long-term fault tolerance, the storage system must have a self-repair service that continuously reconstructs lost fragments of redundancy. The speed of this reconstruction process is crucial for the data survival. In [93] , we propose a new analytical framework, based on queuing models, to estimate the repair time and the probability of data loss. This model takes into account the correlation of concurrent repairs. The models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the Grid'5000 test-bed platform. Recently, the Regenerating Codes were proposed as an improvement over classical replication and erasure codes to introduce redundancy. These codes make a better use of the available bandwidth when reconstructing the missing information. In [50] , we propose a new code based on a hybrid approach, Double Coding, and compare it to existing codes from the point of view of availability, durability and storage space.

Well Balanced Designs for Data Placement

In collaboration with MAESTRO. The problem we consider in [88] is motivated by data placement, in particular, data replication in video on-demand systems. We are given a set $V$ of $n$ servers and $b$ files (data, documents). Each file is replicated on exactly $k$ servers. A placement consists in finding a family of $b$ subsets of $V$ (representing the files) called blocks each of size $k$. Each server has some probability to fail and we want to find a placement which minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than that of any other placement for any value of the probability of failure). We show that the conjecture is true if there exists a well balanced design, that is a family of blocks, such that each $j$-element subset of $V$ , $1\le j\le k$, belongs to the same or almost the same number of blocks (difference at most one). The existence of well balanced designs is a difficult problem as it contains as subproblem the existence of Steiner systems. We completely solve the case $k=2$ and give bounds and constructions for $k=3$ and some values of $n$ and $b$.

Peer-Assisted Time-shifted Streaming Systems: Design and Promises

Time-shifted streaming (or catch-up TV) allows viewers to watch their TV programs within an expanded time window. In [71] , we emphasize the challenging characteristics of time-shifted TV systems that prevent known delivery systems to be used. We model time-shifted TV as multiple-interval graph, then we present a Peer-Assisted Catch-Up Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catch-up TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and self-adaptive unstructured peer-to-peer systems.